The problem of identifying routes through a network subject to a single constraint is well known. For example, Shortest Path First Algorithms by Dijkstra and Bellman-Ford are well known, and both use a single cost, single constraint approach. Dijkstra's method finds the shortest path between a source and any other node in the network.
The problem of routing while considering multiple constraints, while newer than the single constraint problem, has been addressed in a number of ways. See for example Kenji Ishida, Kitsutaro Amano, “A delay-constrained least-cost path routing protocol and the synthesis method”, IEEE conference, 1998; Ariel Orda, “Routing with End to End QoS guarantees in broadband networks”, IEEE conference, 1998; H. F. Salama, D. S. Reeves, Y. Viniotis, “A distributed algorithm for delay-constrained unicast routing”, IEEE conference, 1997; J. Song, H. K. Pung, L. Jacob, “A multi-constrained distributed QoS routing algorithm”, IEEE conference, 2000; S. Chen, K. Nahrstedt, “On finding multi-constrained paths”, IEEE conference, 1998; J. Zhou, “A new distributed routing algorithm for supporting delay-sensitive applications”, ICCT, 1998.
Most of these approaches use the Dijkstra or Bellman-Ford algorithms as a base algorithm to find a sub-optimal path.
Typical IGP (Internal Gateway Protocol) routing protocols such as OSPF (Open Shortest Path First) advertise a single link metric termed “administrative cost”. The default link metric in some cases for this “administrative cost” is the inverse of link bandwidth. Other implementations may use monetary cost, propagation delay etc.
IGP-TE (traffic engineering extension to IGP) adds one more metric which can be advertised within a network. In general, the TE-metric is used to carry any arbitrary metric for constraint-based routing of a set of LSPs (Label Switched paths) needing optimization. The current common practice is to use the IGP metric as a second TE metric, see e.g. IEFT draft “Use of IGP Metric as a second TE Metric” by Francois Le Faucheur et al (expires April 2002) which can be found at http://search.ietf.org/internet-drafts/draft-lefaucheur-te-metric-igp-01.txt
Proposals have also been made to extend the number of TE metrics which are to be advertised up to three, see e.g. IEFT draft “Multiple metrics for Traffic Engineering with IS-IS and OSPF” by Don Fedyk et al (expired May 2001) which can be found at http://search.ietf.org/internet-drafts/draft-fedyk-isis-ospf-te-metrics-01.txt
The cost associated with a path between a source and destination is the sum of the costs of the links that constitute the entire path. Existing proposals recommend not to strive for optimization of both the TE metric and the IGP metric during path computation for a given LSP. This is known to be an NP-complete (non-polynomial complete) problem.
Thus there is a need for heuristic strategies and systems for performing multi-constraint routing to minimize the cost for the entire path.